package bfs;

import org.junit.Test;

import java.util.*;

// 本题不能用DFS, 因为要求最小值.
public class OpenTheLock752 {

    @Test
    public void test() {
        openLock(new String[]{"0201","0101","0102","1212","2002"}, "0202");
        openLock(new String[]{"8888"}, "0009");
        openLock(new String[]{"8887","8889","8878","8898","8788","8988","7888","9888"}, "8888");
    }

    public int openLock(String[] deadends, String target) {
        Integer[] d = new Integer[deadends.length];
        for (int i = 0; i < deadends.length; i++) {
            d[i] = Integer.valueOf(deadends[i]);
        }
        return openLock(d, Integer.parseInt(target));
    }

    public int openLock(Integer[] deadends, int target) {
        Set<Integer> deads = new HashSet<>(Arrays.asList(deadends));
        if (deads.contains(0)) {
            System.out.format("target: %04d, steps: %d\n", target, -1);
            return -1;
        }
        Set<Integer> visited = new HashSet<>(10000*3/2);
        Queue<Integer> q = new LinkedList<>();
        q.offer(0); //0000
        visited.add(0);

        int steps = 0;
        while (!q.isEmpty()) {
            int count = q.size();
            for (int i = 0; i < count; i++) {
                int n = q.poll();
                //visited.add(n); //不要再这里判断,一定要放到产生分支的地方
                if (n == target) {
                    System.out.format("target: %04d, steps: %d\n", target, steps);
                    return steps;
                }
                for (int j = 1; j <= 1000; j *= 10) {
                    Integer n1 = increaseAt(n, j);
                    if (!deads.contains(n1) && !visited.contains(n1)) {
                        q.offer(n1);
                        visited.add(n1); //一定要在这里加, 否则产生太多重复分支, 导致q一直膨胀
                    }

                    n1 = decreaseAt(n, j);
                    if (!deads.contains(n1) && !visited.contains(n1)) {
                        q.offer(n1);
                        visited.add(n1);
                    }
                }
            }
            steps++;
        }
        System.out.format("target: %04d, steps: %d\n", target, -1);
        return -1;
    }

    int increaseAt(int n, int base) {
        int k = (n / base) % 10;
        if (k < 9) {
            return n += base;
        } else {
            return n -= 9*base;
        }
    }

    int decreaseAt(int n, int base) {
        int k = (n / base) % 10;
        if (k > 0) {
            return n -= base;
        } else {
            return n += 9*base;
        }
    }
}
